package com.cqs.leetcode.backtrack;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * lixw
 * 2021/11/9
 **/
public class ZumaGame {

    private int min = Integer.MAX_VALUE;

    public int findMinStep(String board, String hand) {
        min = Integer.MAX_VALUE;
        backtrace(board, new StringBuilder(hand), new boolean[hand.length()]);
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private void backtrace(String board, StringBuilder hand, boolean[] used) {
        if (board.length() == 0) {
            min = Math.min(min, used.length - hand.length());
            return;
        }
        //减枝
        if (min <= used.length - hand.length()) {
            return;
        }
        for (int i = 0; i < hand.length(); i++) {
            if (used[i]) continue;
            char c = hand.charAt(i);
            used[i] = true; //用
            hand.deleteCharAt(i);
            //放在最前面 'x'YxYYxx  N +1 个位置
            for (int j = 0; j <= board.length(); j++) {
                StringBuilder newBoard = new StringBuilder(board).insert(j, c);
                //消消乐" 增加c字符之后，进行消除元素
                backtrace(zuma(newBoard, j).toString(), hand, used);
            }
            hand.insert(i, c); //不用
            used[i] = false;
        }
    }


    private StringBuilder zuma(StringBuilder board, int j) {
        if (board.length() < 2) return board;
        //j的左边
        int l = j;
        while (l - 1 >= 0 && board.charAt(l - 1) == board.charAt(j)) {
            --l;
        }
        int r = j;
        while (r + 1 < board.length() && board.charAt(r + 1) == board.charAt(j)) {
            ++r;
        }
        if (r - l + 1 >= 3) {
            board.delete(l, r+1);
            j = Math.max(0, l - 1);
            return zuma(board, j);
        }
        return board;
    }

    public static void main(String[] args) {
        ZumaGame z = new ZumaGame();
        Map<StringBuilder,String> cases = new LinkedHashMap<>();
        cases.put(new StringBuilder("WRRBBW"),"RB");
        cases.put(new StringBuilder("WWRRBBWW"),"WRBRW");
        cases.put(new StringBuilder("G"),"GGG");
        cases.put(new StringBuilder("WRRBBRWW"),"WRBRW");
        cases.put(new StringBuilder("RRBBRWW"),"WRBRW");
        cases.put(new StringBuilder("RBYYBBRRB"),"YRBGB");
        cases.forEach((k,v)-> System.out.println(k + ":" + v  + " ---> " +   z.findMinStep(k.toString(),v)));

    }
}
